package com.qfedu.entity.course06;

import java.util.LinkedList;
import java.util.Queue;

/**
 *
 */
public class MaxLevel {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftTreeDepth = maxDepth(root.left);
        int rightTreeDepth = maxDepth(root.right);
        return Math.max(leftTreeDepth, rightTreeDepth) + 1;
    }

    public int maxDepthNonRecursive(TreeNode root) {
        if (root == null) {
            return 0;
        } // 考虑树为空的特殊情况 BFS无法自动处理
        Queue<TreeNode> queue = new LinkedList<>();// 使用队列来记录各层节点
        queue.offer(root);// 根节点入队
        int res = 0;// 目标值
        while (!queue.isEmpty()) { // 判断是否还有没有遍历完的节点
            int size = queue.size(); // 开始遍历新一层节点前，队列里即为新一层全部节点 
            while (size > 0) {  // 需将这一层节点全都遍历完
                TreeNode node = queue.poll();// 遍历节点
                if (node.left != null) {
                    queue.offer(node.left);// 左子树入队列
                }
                if (node.right != null) {
                    queue.offer(node.right);// 右子树入队列
                }
                size--;
            }
            res++;// 新一层节点遍历完成，目标值 +1
        }
        return res;
    }
}
